In pattern recognition, there are times when the candidates of a pattern recognition result with respect to an input signal are output using a weighted finite state automaton (WFSA) or an equivalent model to a WFSA. For example, in speech recognition, there are times when a word lattice is output as the result of recognizing an input speech. The word lattice can be expressed as a WFSA by assigning words to input symbols while using word scores as weights.
In pattern recognition, instead of outputting only a single most plausible result corresponding to the input signal, there are times when plausible results from the most plausible result to the N-th most plausible result (where N is an integer equal to or greater than 2) are output. As a result of outputting N number of results, even if the most plausible result is not correct, the user can correct the error by selecting a plausible result from the second plausible result onward. Moreover, if the plausibility is recalculated using a different model, then the most plausible result can be replaced with the plausible result of recalculation. In order to output N number of results, the WFSA obtained from the input signal is searched and N-th best path needs to be found from among the paths present from the initial state to final states.
Meanwhile, there are times when the N-th best path is required in a situation other than pattern recognition. For example, it is possible to consider a case in which N number of paths from a particular railway station to a different railway station are to be displayed in ascending order of the travel time. In that case, with the travel time between the railway stations serving as the weight, either a WFSA can be created in which the station names are assigned to input symbols or an equivalent model to that WFSA can be created, and the N-th best path can be found.
Sometimes, a WFSA includes a plurality of paths in which an identical input symbol string can be obtained. Such a WFSA is called a non-deterministic weighted finite state automaton (a non-deterministic WFSA). However, even if N number of paths are found in order of most suitable weights from such a non-deterministic WFSA, there are times when the paths having different input symbol strings are smaller in number than the number N. Usually, when N number of results are required, it is necessary to output N number of different input symbol strings. For example, consider a case in which three results of pattern recognition are displayed, that is, three input symbol strings are displayed as selection candidates to the user. If all the three displayed results are identical, then selection of any one of the candidates leads to the same result. Hence, it is meaningless to display the selection candidates. Thus, it is necessary to output a plurality of non-duplicative input symbol strings in order of most suitable weights of the corresponding paths.
However, in the case in which a WFSA has empty (ε) input symbols assigned therein, it becomes difficult to find out a plurality of non-duplicative input symbol strings.